#include <limits.h>  // INT_MIN,INT_MAX
#include <math.h>    // abs,pow

#include <algorithm>      // sort
#include <iostream>       // cout,cin
#include <numeric>        // accumulate
#include <string>         // string
#include <unordered_map>  // unordered_map
#include <unordered_set>  // unordered_set
#include <vector>         // vector

using namespace std;

// 链表结点的数据结构
struct ListNode {
    int val;
    ListNode* next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode* next) : val(x), next(next) {}
};

class Node {
   public:
    int val;
    Node* next;

    Node() {}

    Node(int _val) {
        val = _val;
        next = NULL;
    }

    Node(int _val, Node* _next) {
        val = _val;
        next = _next;
    }
};

// 如果x是2的幂则返回True，否则返回False
bool IsPowerOf2(int x) { return (x & (x - 1)) == 0; }

class Solution {
   public:
    Node* insert(Node* head, int insertVal) {
        // 处理链表为空的情况
        if (!head) {
            Node* node = new Node(insertVal);
            node->next = node;
            return node;
        }

        // 寻找循环链表最小值结点
        int min_val = head->val, max_val = head->val;
        Node* node = head->next;
        Node *start = head, *end = head;
        while (node != head) {
            if (node->val < min_val) {
                start = node;
                min_val = node->val;
            }
            if (node->val >= max_val) {
                end = node;
                max_val = node->val;
            }
            node = node->next;
        }

        // 处理需要插入在头尾之间的情况
        if (insertVal <= start->val || insertVal >= end->val) {
            Node* insert_node = new Node(insertVal);
            insert_node->next = end->next;
            end->next = insert_node;
            return head;
        }

        // 处理插入在其他位置的情况
        node = start;
        while (node != end) {
            int node_val = node->val;
            int next_val = node->next->val;
            // 当前正在递增的情况
            if (node_val <= insertVal && insertVal <= next_val) {
                Node* insert_node = new Node(insertVal);
                insert_node->next = node->next;
                node->next = insert_node;
                return head;
            }
            node = node->next;
        }

        return head;
    }
};

int main() {
    Solution solution;
    return 0;
}